学动规的过程中，分清动规、贪心、递归、递推是一个漫长的过程，而且正如初学动规时队长所说，动规的问题也许难点并不在动规本身，而更难的是如何判断一个问题是动规问题。今天小有所得，遂记之。
1、01背包问题是不能用贪心算法的，原因是物品的选择必须依赖于子问题，而贪心问题的两个条件之一是贪心选择问题性，
即：选择如何做时，只考虑对当前问题最佳的选择而不考虑子问题的结果。
举个例子，如果有一个容量等于500的背包，你有三个东西，价值500重量300，价值500重量500，价值100重量200.
用贪心的话，那个重量200的东西就放不进去，而用动规才行
2、部分背包问题是贪心问题
3、01背包问题具有最优子结构性质，这是动态规划的基础
4、01背包问题是多阶段决策过程，这是动规的产生动机
/ 01背包问题 程序中 S 是物品的数目 W 是背包的最大重量 p[i] 是第i个物品的价值 w[i] 是第i个物品的重量 f[i][j] 是前i个物品装到最大重量是j的包里的最大价值 算法；动态规划 /
#include <iostream>
using namespace std;
int S,W,i,j,w[101],p[101],f[101][101];
int main()
{
cin>>S>>W;
for (i=1; i<=S; i++) cin>>p[i]>>w[i];
for (i=1; i<=S; i++)
{
for (j=1; j<=W; j++)
{
if (w[i]>j) f[i][j]=f[i-1][j];
else f[i][j]= f[i-1][j-w[i]]+p[i]>f[i-1][j] ? f[i-1][j-w[i]]+p[i] : f[i-1][j];
}
}
cout<<f[S][W]<<endl;
system("pause");
return 0;
}
/ 部分背包问题 程序中 S 是物品的数目 W 是背包的最大重量 p[i] 是第i个物品的价值 w[i] 是第i个物品的重量 a[i]=p[i]/w[i] 是第i个物品的单位价值 算法；贪心策略 /
#include <iostream>
using namespace std;
int v,S,W,i,w[101],p[101];
double u,maxx,a[101];
void qsort(int i,int j)
{
int s,t,v;
double x,u;
s=i; t=j; x=a[(i+j)/2];
do {
while (a[s]<x) s++;
while (a[t]>x) t--;
if (s<=t) {
u=a[s]; a[s]=a[t]; a[t]=u;
v=p[s]; p[s]=p[t]; p[t]=v;
v=w[s]; w[s]=w[t]; w[t]=v;
s++;t--;
}
}
while (s<t);
if (i<t) qsort(i,t);
if (s<j) qsort(s,j);
return;
}
int main()
{
cin>>S>>W;
for (i=1; i<=S; i++)
{
cin>>p[i]>>w[i];
a[i]=(p[i]+0.00000)/w[i];
}
qsort(1,S);
i=S;
maxx=0;
while (W>=w[i])
{
W=W-w[i];
maxx=maxx+p[i];
i--;
}
maxx=maxx+(W*p[i]+0.00000)/w[i];
cout<<maxx<<endl;
system("pause");
return 0;
}